In a network of communicating devices, such as for example the Internet, or a communication network coupled thereto (such as for example an enterprise network, a wireless communication system, or any other type of computer network or communication system), the devices are each generally identified by a substantially unique name, such as for example the 4-octet address associated with devices by the IP (Internet Protocol) protocol (version 4), and any variants thereof. These substantially unique names are generally used by routing or switching devices within the network to direct messages (using either circuit-based or packet-based techniques) from their sources to their destinations.
The routing and switching devices, or at least the subnet thereof (sometimes referred to herein as “the network”), are at least collectively aware of the network topology (which devices are coupled to which other devices) and the network topography (which connections between devices are relatively fast or slow, reliable or not, or exhibit other features relevant to network communication, such as for example a measure of quality of service, sometimes called “QoS”). While this information is generally available throughout the network for communication purposes, the physical locations of devices coupled to the network or using it for communication are not so freely available. Identifying physical location in response to network address information—and possibly other information, such as metadata about the communicating device or its users' habits and practices—is sometimes called “geolocation”, it is also sometimes called “IP geolocation”, or other terms or phrases.
Relatively precise and reliable geolocation might be desired for a device coupled to such a network for a variety of reasons, such as one or more of the following:                directing advertisements or other communications to recipients in selected geographic regions, sometimes referred to herein as “geotargeting”, “IP geotargeting”, or other terms or phrases;        determining a most probable set of locations for that device, such as to locate lost nodes or to rule out locations for lost nodes, such as in a search-and-rescue environment in a wireless environment distributed over a relatively large region, or to locate rogue nodes or to rule out locations for rogue nodes, such as in a hostile electromagnetic environment as one might find due to criminal, espionage, or military activity;        determining an external boundary of a region or area within which that device, according to received data, must necessarily be located, such as in a search-and-rescue environment or a law enforcement environment, or similarly, providing sufficient evidence or proof that a designated device was or was not located within a designated region, or at a specific location, within a designated time period, such as in a legal proof environment or a network trouble-shooting environment;        locating failed nodes and communication paths within such a network, or at least locating a most probable set of such failed nodes and communication paths within such a network, such as in an environment in which nodes cannot be found for communication or such as in an environment in which communication with nodes is uncertain; and        identifying, with at least some degree of specificity, a physical, geographic path through which a designated set of messages flow through that network, such as in an environment in which the physical location of network traffic is deemed important, such as a network trouble-shooting environment, a search-and-rescue environment (particularly if communication with one or more rescue workers is lost or unreliable), or such as when communicating nodes in the network are moving, such as in an environment in which tracking the location of such nodes from time to time is desired, such as an air-traffic control or fleet management environment.        
Known methods include determining the physical location of a device in a computer network using triangulation on the surface of a sphere (approximately the shape of the Earth), in response to communication delay to-and-from the device from three or more known locations. See, for example, U.S. Pat. No. 6,947,978 B2. While these known methods can generally achieve their purpose of providing approximate physical locations of such devices, they are generally only able to designate an area of the Earth's surface as the possible locations of the device. These approximate physical locations have a margin of error which is often higher than desirable, and often provide insufficient accuracy, for many purposes. The granularity of these measurements is often higher than desirable, given the relatively rapid propagation of signals within the network, with the result that precision of measurement is extremely difficult to obtain. Often the location of the device can only be determined to within an area of several thousand square miles. This is often deemed inadequate for many uses of geolocation described herein. Moreover, these measurements serve only to designate a possible region for the geolocated element; they do not provide any substantial information about probability of location within that possible region.
Known methods include using statements by third parties about the location of the device. For example, the Internet “Whois” record for the domain name associated with the device shows a postal address for the party that administers the subnet where that device is found. See, for example, U.S. Pat. No. 6,684,250 B2. While these known methods can generally achieve their purpose of providing better physical locations of such devices than pure triangulation, they are subject to several drawbacks: (1) the Whois record shows a postal address for an administrator, which is no guarantee of the location of the actual device itself; (2) Whois records might be inaccurate or even deliberately false; (3) Whois records are often deemed inadequate information or insufficiently certain to provide useful geolocation information, e.g., for police or detective work, or for evidence in court. These problems appear inherent to information supplied about the device from a third party, or provided voluntarily, or provided by a human being, rather than directly obtained from interaction with the device, and are not specific to “Whois” records.
Known methods include determining a matrix of minimum communication times between (1) a set of multiple network stations, and (2) a set of endpoint nodes. Both the former and the latter are at known locations. A vector of communication times from the network stations to the target device is measured, and the target device is presumed to be at the same location as the endpoint whose vector of communication times (from the network stations) most closely matches the measured vector. See, for example, U.S. Pat. No. 6,947,978 B2. While these known methods can generally achieve their purpose of providing better physical locations of such devices than pure triangulation, they are subject to the drawback that an amount of communication effort diverted to geolocation is relatively large. Neither network traffic to the target device nor network traffic overall are minimized, with the effect that both the target device is burdened by the effort, and with the effect that geolocation efforts become relatively more difficult with network size.
Moreover, obtaining a vector of such communication times involves measuring one or more distances to endpoint nodes which are at known locations. It sometimes occurs that such known locations are not as prevalent as desirable. It often occurs that such known locations are not conveniently located, or even located anywhere reasonably near the target device, either locality within the connectivity of the network or locality within physical space. Preparing a set of such known locations ahead of time involves significant network communication, as well as effort and time, and has a substantial chance of failing to find enough such known locations ahead of time for a target location that is unknown ahead of time.
Known methods generally suffer from the drawbacks that they do not significantly address questions regarding the network topology or network topography, such as, whether the network has adequate connectivity, whether the network topology or network topography have changed significantly over time, what the communication limits are of the network, and other information related to trouble-shooting the subnet of communication and routing devices for the network. Moreover, known methods generally suffer from the drawbacks that they do not generally provide any convenient method for assigning priority to one or more determined locations or determined regions. For example, known methods generally provide only a set of points or regions where the geolocated target device might be found, without relative probability of one or more of those points, or one or more subsets of those regions, being factually accurate or useful for the purpose for which geolocation was used.
Some, not necessarily all, methods are described in the following documents:                U.S. Pat. No. 6,684,250 B2, issued Jan. 27, 2004, in the name of inventors Anderson, et al., titled “Method and apparatus for estimating a geographic location of a networked entity”, believed to be assigned to Quova, Inc., of Mountain View, Calif.; and        U.S. Pat. No. 6,947,978 B2, issued Sep. 20, 2005, in the name of inventors Huffman, et al., titled “Method for geolocating logical network addresses”, assigned to the United States, as represented by the Director, National Security Agency.        Readers are encouraged and exhorted to make their own evaluation of known methods.        